Skip to main content

Local Algorithms for Graphs

Iframe Pdf Item Preview

texts

Local Algorithms for Graphs

by
David Gamarnik; Mathieu Hemery; Samuel Hetterich

Publication date
Usage
Attribution-Noncommercial-Share Alike 3.0Creative Commons Licensebyncsa
Topics
Data Structures and Algorithms, Computing Research Repository, Disordered Systems and Neural Networks, Condensed Matter
Publisher
arXiv.org
Collection
arxiv; journals
Contributor
Internet Archive
We are going to analyze local algorithms over sparse random graphs. These algorithms are based on local information where local regards to a decision made by the exploration of a small neighbourhood of a certain vertex plus a believe of the structure of the whole graph and maybe added some randomness. This kind of algorithms can be a natural response to the given problem or an efficient approximation such as the Belief Propagation Algorithm.

Notes

Chapter of "Statistical Physics, Optimization, Inference, and Message-Passing Algorithms", Eds.: F. Krzakala, F. Ricci-Tersenghi, L. Zdeborova, R. Zecchina, E. W. Tramel, L. F. Cugliandolo (Oxford University Press, to appear)

Addeddate
2018-06-30 07:13:36
External-identifier
urn:arXiv:1409.5214[arXiv]
Identifier
arxiv-1409.5214
Scanner
Internet Archive Python library 1.7.0.dev2
Source
http://arxiv.org/abs/1409.5214

plus-circle Add Review
comment
Reviews

There are no reviews yet. Be the first one to write a review.

22 Views

DOWNLOAD OPTIONS

download 1 file
PDF download
download 1 file
TORRENT download
download 6 Files
download 6 Original
SHOW ALL

IN COLLECTIONS

Arxiv.org Journals

Uploaded by arkiver2 on

SIMILAR ITEMS (based on metadata)

Terms of Service (last updated 12/31/2014)